home *** CD-ROM | disk | FTP | other *** search
Text File | 1997-06-28 | 2.7 KB | 148 lines | [TEXT/CWIE] |
- // RedBlackKeyTree.cp
-
- #ifndef RedBlackKeyTree_h
- #include "RedBlackKeyTree.h"
- #endif
- #ifndef RedBlackKey_h
- #include "RedBlackKey.h"
- #endif
- #ifndef ElementNotFound_h
- #include "ElementNotFound.h"
- #endif
-
- template < class Key >
- RedBlackKey<Key> *RedBlackKeyTree<Key>::DownCast( NodeBase *n )
- {
- return static_cast< Node* >( n );
- }
-
- template < class Key >
- const RedBlackKey<Key> *RedBlackKeyTree<Key>::DownCast( const NodeBase *n )
- {
- return static_cast< const Node* >( n );
- }
-
- template < class Key >
- void RedBlackKeyTree<Key>::Remove( Node& node )
- {
- TreeBase::Remove( node );
- }
-
- template < class Key >
- void RedBlackKeyTree<Key>::Add( Node& node )
- {
- if ( IsEmpty() )
- {
- TreeBase::Add( node, atRoot );
- return;
- }
-
- Node *position = Root();
-
- while ( true )
- if ( node >= *position )
- {
- if ( position->HasRightChild() )
- position = position->Right();
- else
- {
- TreeBase::Add( node, after, *position );
- return;
- }
- }
- else
- {
- if ( position->HasLeftChild() )
- position = position->Left();
- else
- {
- TreeBase::Add( node, before, *position );
- return;
- }
- }
- }
-
- template < class Key >
- RedBlackKey<Key> *RedBlackKeyTree<Key>::FindTopmost( const Key& k ) const
- {
- Node *position = const_cast<Node *>( Root() );
- while ( position != 0 && *position != k )
- if ( *position > k )
- position = position->Left();
- else
- position = position->Right();
-
- return position;
- }
-
- template < class Key >
- RedBlackKey<Key>& RedBlackKeyTree<Key>::Lookup( const Key& k ) const
- {
- Node *position = FindTopmost( k );
- if ( position == 0 )
- throw ElementNotFoundAt<Key>( k );
- return *position;
- }
-
- template < class Key >
- RedBlackKey<Key> *RedBlackKeyTree<Key>::FindFirst( const Key& k ) const
- {
- Node *result = FindTopmost( k );
-
- if ( result == 0 )
- return 0;
-
- Node *position = result->Left();
-
- while ( position != 0 )
- if ( *position == k )
- {
- result = position;
- position = position->Left();
- }
- else
- position = position->Right();
-
- return result;
- }
-
- template < class Key >
- RedBlackKey<Key> *RedBlackKeyTree<Key>::FindLast( const Key& k ) const
- {
- Node *result = FindTopmost( k );
-
- if ( result == 0 )
- return 0;
-
- Node *position = result->Right();
-
- while ( position != 0 )
- if ( *position == k )
- {
- result = position;
- position = position->Right();
- }
- else
- position = position->Left();
-
- return result;
- }
-
- template < class Key >
- bool RedBlackKeyTree<Key>::Valid() const
- {
- if ( !TreeBase::Valid() )
- return false;
-
- const Node *n = First();
- while ( n != 0 )
- {
- const Node *next = n->Next();
- if ( next != 0 && *next < *n )
- return false;
- n = next;
- }
-
- return true;
- }
-